/**
 * 子集 - 动态规划
 *
 * 思想 将求子集 分解为 求单个子集数量 从而 求解 多个子集
 * @see https://leetcode.cn/problems/subsets/submissions/
 * @example 输入：num = [1,2,3]
 * 输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
 * @param {number[]} num
 */
function subsets(num: number[]) {
  /**
   * 初始空集
   */
  const result: number[][] = [[]]

  for (let i = 0; i < num.length; i++) {
    /**
     * 真子集公式 2^n
     * 计算每一项 i 长度 真子集个数
     */
    const end = 2**i
    const element = num[i];

    for (let j = 0; j < end; j++) {
      /**
       * 当前子集 [start + j] = j 的子集 + 当前元素
       */
      result[end + j] = result[j].concat(element)
    }
  }

  return result
}

/**
 * 子集 - 回溯
 *
 * 思想 将求子集 抽象为 树 一个子项对应一个树
 */
function subsets2(num: number[]) {
  const result: number[][] = []
  /**
   * 当前结果路径
   */
  const path: number[] = []
  const backtracking = function (start: number) {
    /**
     * 收集结果
     */
    result.push(path.slice())

    if (start > num.length) return

    for (let i = start; i < num.length; i++) {
      const element = num[i]
      // 收集路径
      path.push(element)
      // 继续搜索
      backtracking(i + 1)
      // 回退树
      path.pop()
    }
  }

  backtracking(0)
  return result
}

/**
 * 子集 - 纯数学规律
 */
function subsets3(num: number[]) {
  const result: number[][] = [[]]

  for (let i = 0; i < num.length; i++) {
    const element = num[i];
    const length = result.length
    for (let j = 0; j < length; j++) {
      const item = result[j]
      // 每一项子集 = 已收集子集[j]项 + 当前项
      result.push(item.concat(element))
    }
  }

  return result
}

console.log(subsets([1, 2, 3]))
console.log(subsets2([1, 2, 3]))
console.log(subsets3([1, 2, 3]))
